ON SINGLE DETECTING TEST SETS FOR CIRCUITS OF SWITCHING TYPE 

Romanov Dmitriy Sergeevich, Candidate of physical and mathematical sciences, associate professor, sub-department of mathematical cybernetics, Moscow State University named after M. V. Lomonosov (1 Leninskie gory street, Moscow, Russia), romanov@cs.msu.ru
Romanova Elena Yur'evna, Candidate of pedagogical sciences, associate professor, sub-department of applied mathematics, Russian State Social University (building 1, 4 Wilgelma Pika street, Moscow, Russia), klenar2001@mail.ru

519.718

Background. Testing of discrete models of switching-type circuits is an important theoretical problem with applications to testing and verification of VLSI. The article considers a class of so-called generalized iterative switching circuits (GISC). This class consists of classical switching circuits (SC), however, it allows the usage of superpositions. The aim of this work is to demonstrate that for an arbitrary nonconstant Boolean function it is possible to construct a circuit realizing or modeling this function (in the latter case the circuit realizes a function after substitution constants instead of some input variables), and allowing a small single detecting test set.
Materials and methods. The authors used circuit design methods based on the Zhegalkin polinomials.
Results. It has been established that for an arbitrary nonconstant Boolean function f depending on n variables there exist testable GISCs realizing f and admitting a) the single fault detecting test set (under homogeneous faults – closures or breakings) of power O(1), b) the single fault detecting test set of power O(n). Moreover, it has proved that for an arbitrary nonconstant Boolean function f depending on n variables there exist testable GISCs and SCs modeling f and admitting the single fault detecting test set of power O(1).

boolean function, switching circuit, generalized iterative switching circuit, detecting test set.

1. Red'kin N. P. Nadezhnost' i diagnostika skhem [Reliability and diagnostics of circuits]. Moscow: Izd-vo MGU,1992, 192 p.
2. Lozhkin S. A. Lektsii po osnovam kibernetiki [Lectures on basic cybernetics]. Moscow: MAKS Press,2004,256p.
3. Lozhkin S. A., Kondratov A. V. Prikladnaya matematika i informatika [Applied mathe-matics and informatics]. Issue 21. Moscow: MAKS Press, 2005, pp. 102–110.
4. Chegis I. A., Yablonskiy S. V. Trudy MIAN SSSR [Proceedings of Steklov Mathematical Institute of the USSR Academy of Sciences]. 1958, vol. LI, pp. 270–360.
5. Madatyan Kh. A. Problemy kibernetiki [Problems of cybernetics]. Issue 23. Moscow: Nauka,1970,pp.103–118.
6. Madatyan Kh. A. Sbornik rabot po matematicheskoy kibernetike [Collected works on mathematical cybernetics]. Moscow: VTs AN SSSR, 1981, pp. 77–86.
7. Red'kin N. P. Metody diskretnogo analiza v issledovanii ekstremal'nykh struktur [Methods of discrete analysis in research of extreme structures]. Issue 39. Novosibirsk: Izd-vo IM SO AN SSSR, 1983, pp. 80–87.
8. Red'kin N. P. Metody diskretnogo analiza v optimizatsii upravlyayushchikh system [Methods of discrete analysis in optimization of control systems]. Issue 40. Novosibirsk: Izd-vo IM SO AN SSSR, 1983, pp. 87–99.
9. Rybko A. I. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernet-ics]. Issue 1. Moscow: Nauka, 1988, pp. 168–190.
10. Romanov D. S. Uchenye zapiski Kazanskogo universiteta. Ser. Fiziko-matematicheskie nauki [Proceedings of Kazan University. Series: physical and mathematical sciences]. 2014, vol. 156, bk. 3, pp. 110–115.